/*
 * list.c
 *
 *  Created on: Feb 26, 2011
 *      Author: thienlong
 */
#include "list.h"
#include "error.h"

vector* vector_new(int capacity, eq_fn eqfn, del_fn delfn,
		mem_storage *storage, mem_type type) {
	vector *vec = malloc(sizeof(vector));
	VECTOR_INIT(vec, capacity, eqfn, delfn, storage, type);
	return vec;
}

void ENSURE_CAPACITY(vector *vec, int min_cap) {
	int old_cap = (vec)->capacity;
	if (min_cap > old_cap) {
		int new_cap = (old_cap * 3) / 2 + 1;
		if (new_cap < min_cap)
			new_cap = min_cap;
		(vec)->items = realloc((vec)->items, new_cap * sizeof(object));
		if (vec->items == NULL) {
			fprintf(stderr, "can't realloc size %lu", new_cap * sizeof(object));
			assert((vec)->items);
		}
		(vec)->capacity = new_cap;
	}
}

#define CHECK_RANGE(vec, index) { \
	if (index > vec->size || index < 0) { \
			AL_Error(AL_StsOutOfRange, "index out of bound"); \
	} \
}

void vector_add(vector *v, object obj) {
	ENSURE_CAPACITY(v, v->size + 1);
	v->items[(v->size)++] = obj;
}

void vector_insert(vector *v, int index, object obj) {
	CHECK_RANGE(v, index);
	ENSURE_CAPACITY(v, v->size + 1);
	int i = v->size;
	for (; i > index; --i) {
		v->items[i] = v->items[i - 1];
	}
	v->items[index] = obj;
	++(v->size);
}

object vector_set(vector *v, int index, object obj) {
	CHECK_RANGE(v, index);
	object old = v->items[index];
	v->items[index] = obj;
	return old;
}

object vector_get(vector *v, int index) {
	CHECK_RANGE(v, index);
	return v->items[index];
}

object vector_del(vector *v, int index) {
	CHECK_RANGE(v, index);
	object old = v->items[index];
	int i = index;
	int n = v->size - 1;
	for (; i < n; ++i) {
		v->items[i] = v->items[i + 1];
	}
	--(v->size);
	v->items[v->size] = NULL;
	return old;
}

bool vector_remove(vector *v, object obj) {
	int index = 0;
	for (; index < v->size; ++index) {
		if (v->eqfn(obj, v->items[index])) {
			if (v->delfn) {
				v->delfn(v->items[index], v->storage, v->mtype);
			}
			int i = index;
			int n = v->size - 1;
			for (; i < n; ++i) {
				v->items[i] = v->items[i + 1];
			}
			--(v->size);
			v->items[v->size] = NULL;
			return true;
		}
	}
	return false;
}

/**
 * removes the last element of a given vector
 */
object vector_pop(vector *v) {
	if (v->size) {
		--(v->size);
		object obj = v->items[v->size];
		v->items[v->size] = NULL;
		return obj;
	}
	return NULL;
}

object vector_detach(vector *v, object obj) {
	int index = 0;
	for (; index < v->size; ++index) {
		if (v->eqfn(obj, v->items[index])) {
			object result = v->items[index];
			int i = index;
			int n = v->size - 1;
			for (; i < n; ++i) {
				v->items[i] = v->items[i + 1];
			}
			--(v->size);
			v->items[v->size] = NULL;
			return result;
		}
	}
	return NULL;
}

bool vector_detach_ref(vector *v, object obj) {
	int index = 0;
	int firstocur = -1;
	int ocurnum = 0;
	int size = v->size;
	for (; index < size; ++index) {
		if (obj == v->items[index]) {
			v->items[index] = NULL;
			if (firstocur == -1) {
				firstocur = index;
			}
			++ocurnum;
		}
	}
	if (ocurnum) {
		index = firstocur + 1;
		while (index < size) {
			if (v->items[index]) {
				v->items[firstocur] = v->items[index];
				++index;
				++firstocur;
			} else {
				++index;
			}
		}
		v->size = size - ocurnum;
		return true;
	}
	return false;
}

int vector_first(vector *v, object obj) {
	int index = 0;
	for (; index < v->size; ++index) {
		if (v->eqfn(obj, v->items[index])) {
			return index;
		}
	}
	return -1;
}

int vector_last(vector *v, object obj) {
	int index = v->size - 1;
	for (; index >= 0; --index) {
		if (v->eqfn(obj, v->items[index])) {
			return index;
		}
	}
	return -1;
}

void vector_clear(vector *v, bool del) {
	if (del && v->delfn) {
		int index = 0;
		for (; index < v->size; ++index) {
			v->delfn(v->items[index], v->storage, v->mtype);
		}
	}
	v->size = 0;
}

void vector_free(vector **v) {
	vector *vec = *v;
	if (*v != NULL) {
		*v = NULL;
		vector_clear(vec, true);
		free(vec->items);
		free(vec);
	} else {
		AL_Error(AL_StsNullPtr, "null point exception");
	}
}

void vector_free_ref(vector **v) {
	vector *vec = *v;
	if (*v != NULL) {
		*v = NULL;
		int index = 0;
		object obj = NULL;
		int i = 0;
		int size = vec->size;
		for (; index < size; ++index) {
			obj = vec->items[index];
			if (obj) {
				//detach reference of this %obj
				for (i = index + 1; i < size; ++i) {
					if (obj == vec->items[i]) {
						vec->items[i] = NULL;
					}
				}
				vec->delfn(obj, vec->storage, vec->mtype);
			}
		}
		free(vec->items);
		free(vec);
	} else {
		AL_Error(AL_StsNullPtr, "null point exception");
	}
}

#define QUEUE_CAPACITY_DEFAULT 16
extern array_cqueue* acqueue_new(int capacity) {
	array_cqueue *queue = malloc(sizeof(array_cqueue));
	if (capacity > 0) {
		queue->capacity = capacity;
	} else {
		queue->capacity = QUEUE_CAPACITY_DEFAULT;
	}
	queue->count = 0;
	queue->items = calloc(queue->capacity, sizeof(object));
	pthread_mutex_init(&queue->lock, NULL);
	pthread_cond_init(&queue->not_empty, NULL);
	pthread_cond_init(&queue->not_full, NULL);
	queue->take_idx = 0;
	queue->put_idx = 0;
	return queue;
}

#define INCR(i, qlen) \
if (++(i) == qlen) { \
	(i) = 0; \
}

void ACQUEUE_INSERT_ITEM(array_cqueue *queue, object obj) {
	queue->items[queue->put_idx] = obj;
	INCR(queue->put_idx, queue->capacity);
	++(queue->count);
	pthread_cond_signal(&queue->not_empty);
}

/**
 * Inserts the specified element at the tail of this queue if it is
 * possible to do so immediately without exceeding the queue's capacity,
 * returning <tt>true</tt> upon success and <tt>false</tt> if this queue
 * is full.
 *
 */bool acqueue_add(array_cqueue *queue, object obj) {
	pthread_mutex_lock(&queue->lock);
	if (queue->count == queue->capacity) {
		pthread_mutex_unlock(&queue->lock);
		return false;
	} else {
		ACQUEUE_INSERT_ITEM(queue, obj);
		pthread_mutex_unlock(&queue->lock);
		return true;
	}
}

/**
 * Inserts the specified element at the tail of this queue, waiting
 * for space to become available if the queue is full.
 *
 * @throws InterruptedException {@inheritDoc}
 */
extern void acqueue_put(array_cqueue *queue, object obj) {
	int capacity = queue->capacity;
	pthread_mutex_lock(&queue->lock);
	while (queue->count == capacity) {
		pthread_cond_wait(&queue->not_full, &queue->lock);
	}
	ACQUEUE_INSERT_ITEM(queue, obj);
	pthread_mutex_unlock(&queue->lock);
}

/**
 * Inserts the specified element at the tail of this queue, waiting
 * up to the specified wait time (TimeUnit is second) for space to become available if
 * the queue is full.
 *
 * @throws InterruptedException {@inheritDoc}
 * @throws NullPointerException {@inheritDoc}
 */bool acqueue_offer(array_cqueue *queue, object obj, long timeout) {
	struct timespec ts;
	clock_gettime(CLOCK_REALTIME, &ts);
	ts.tv_sec += timeout;
	return acqueue_insert(queue, obj, &ts);
}

/**
 * Inserts the specified element at the tail of this queue, waiting
 * up to the specified wait time for space to become available if
 * the queue is full. ABSTIME is an
 absolute time specification; zero is the beginning of the epoch
 (00:00:00 GMT, January 1, 1970).
 *
 * @throws InterruptedException {@inheritDoc}
 * @throws NullPointerException {@inheritDoc}
 */bool acqueue_insert(array_cqueue *queue, object obj, struct timespec *abstime) {
	pthread_mutex_lock(&queue->lock);
	int wait_result = 0;
	while (true) {
		if (queue->count != queue->capacity) {
			ACQUEUE_INSERT_ITEM(queue, obj);
			pthread_mutex_unlock(&queue->lock);
			return true;
		}
		if (wait_result == ETIMEDOUT) {
			pthread_mutex_unlock(&queue->lock);
			return false;
		}
		wait_result = pthread_cond_timedwait(&queue->not_full, &queue->lock,
				abstime);
	}
}

/**
 * Extracts element at current take position, advances, and signals.
 * Call only when holding lock.
 */
object ACQUEUE_EXTRACT_ITEM(array_cqueue *queue) {
	object x = queue->items[queue->take_idx];
	queue->items[queue->take_idx] = NULL;
	INCR(queue->take_idx, queue->capacity);
	--(queue->count);
	pthread_cond_signal(&queue->not_full);
	return x;
}

/*Retrieves and removes the head of this queue, or returns null if this queue is empty.

 Returns:
 the head of this queue, or null if this queue is empty*/
object acqueue_remove(array_cqueue *queue) {
	pthread_mutex_lock(&queue->lock);
	if (queue->count == 0) {
		pthread_mutex_unlock(&queue->lock);
		return NULL;
	}
	object x = ACQUEUE_EXTRACT_ITEM(queue);
	pthread_mutex_unlock(&queue->lock);
	return x;
}

/*Retrieves and removes the head of this queue, waiting if necessary until an element becomes available.
 Specified by: take() in BlockingQueue

 Returns:
 the head of this queue*/
object acqueue_take(array_cqueue *queue) {
	pthread_mutex_lock(&queue->lock);
	while (queue->count == 0) {
		pthread_cond_wait(&queue->not_empty, &queue->lock);
	}
	object x = ACQUEUE_EXTRACT_ITEM(queue);
	pthread_mutex_unlock(&queue->lock);
	return x;
}

/*
 Retrieves and removes the head of this queue, waiting up to the specified wait time if necessary for an element to become available.
 Specified by: poll(...) in BlockingQueue

 Parameters:
 timeout how long to wait before giving up, in units of unit
 unit a TimeUnit determining how to interpret the timeout parameter
 Returns:
 the head of this queue, or null if the specified waiting time elapses before an element is available*/
object acqueue_poll(array_cqueue *queue, long timeout) {
	struct timespec ts;
	clock_gettime(CLOCK_REALTIME, &ts);
	ts.tv_sec += timeout;
	return acqueue_pop(queue, &ts);
}

/*
 Retrieves and removes the head of this queue, waiting up to the specified wait time if necessary for an element to become available.
 Specified by: poll(...) in BlockingQueue

 Parameters:
 timeout how long to wait before giving up, in units of unit
 unit a TimeUnit determining how to interpret the timeout parameter
 Returns:
 the head of this queue, or null if the specified waiting time elapses before an element is available*/
object acqueue_pop(array_cqueue *queue, struct timespec *abstime) {
	pthread_mutex_lock(&queue->lock);
	int wait_result = 0;
	while (true) {
		if (queue->count != 0) {
			object x = ACQUEUE_EXTRACT_ITEM(queue);
			pthread_mutex_unlock(&queue->lock);
			return x;
		}
		if (wait_result == ETIMEDOUT) {
			pthread_mutex_unlock(&queue->lock);
			return false;
		}
		wait_result = pthread_cond_timedwait(&queue->not_empty, &queue->lock,
				abstime);
	}
}

/*Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
 Specified by: peek() in Queue

 Returns:
 the head of this queue, or null if this queue is empty*/
object acqueue_peek(array_cqueue *queue) {
	object x = NULL;
	pthread_mutex_lock(&queue->lock);
	if (queue->count != 0) {
		x = queue->items[queue->take_idx];
	}
	pthread_mutex_unlock(&queue->lock);
	return x;
}

/*Returns the number of elements in this queue.
 Specified by: size() in Collection, Overrides: size() in AbstractCollection

 Returns:
 the number of elements in this queue*/
int acqueue_size(array_cqueue *queue) {
	int size = 0;
	pthread_mutex_lock(&queue->lock);
	size = queue->count;
	pthread_mutex_unlock(&queue->lock);
	return size;
}

/**
 * Atomically removes all of the elements from this queue.
 * The queue will be empty after this call returns.
 */
extern void acqueue_clear(array_cqueue *queue, del_fn delcb,
		mem_storage *storage, mem_type type) {
	object* const items = queue->items;
	pthread_mutex_lock(&queue->lock);
	int i = queue->take_idx;
	int k = queue->count;
	int cap = queue->capacity;
	while (k-- > 0) {
		if (delcb) {
			delcb(items[i], storage, type);
		}
		items[i] = NULL;
		INCR(i, cap);
	}
	queue->count = 0;
	queue->put_idx = 0;
	queue->take_idx = 0;
	pthread_cond_broadcast(&queue->not_full);
	pthread_mutex_unlock(&queue->lock);
}
